package month1;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class CourseScheduleI207_06 {
    public static void main(String[] args) {
        System.out.println(canFinish(2, new int[][]{{1, 0}, {0, 1}}));
    }

    /**
     * 简单BFS吧
     * @param numCourses
     * @param prerequisites
     * @return
     */
    static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] edges = new List[numCourses];
        for (int i = 0; i < numCourses; ++i) {
            edges[i] = new LinkedList<>();
        }
        int[] ingrades = new int[numCourses];
        for (int[] prerequisity : prerequisites) {
            edges[prerequisity[1]].add(prerequisity[0]);
            ingrades[prerequisity[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i) {
            if (ingrades[i] == 0) q.offer(i);
        }
        while (!q.isEmpty()) {
            numCourses--;
            int cur = q.poll();
            for (int to : edges[cur]) {
                if (--ingrades[to] == 0) {
                    q.offer(to);
                }
            }
        }
        return numCourses == 0;
    }
}
